import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

// 二叉搜索树
public class BinarySearchTree<T extends Comparable<T>> {
    Node<T> treeRoot;
    class Node<T extends Comparable<T>>{
        T val;
        Node leftChild;
        Node rightChild;
        Node(T val,Node leftChild,Node rightChild){
            this.val=val;
            this.leftChild=leftChild;
            this.rightChild=rightChild;
        }
        Node(T val) {
            this(val, null, null);
        }
    }

    public boolean isLeaf(Node<T> root){
        if(root==null)
            throw new RuntimeException("Null can not justify wether is leaf");
        return root.leftChild==null && root.rightChild==null;
    }



    // 插入node
    public   void insert(T val){
        if(treeRoot==null) {
            treeRoot = new Node<>(val);
            return;
        }
        Node<T> currentNode = treeRoot;
        for(;;){
            if(currentNode.val.compareTo(val)>=0){
                // 向左走
                if(currentNode.leftChild == null){
                    currentNode.leftChild = new Node(val);
                    break;
                }else
                    currentNode = currentNode.leftChild;
            }else if(currentNode.val.compareTo(val)<0){
                // 向右走
                if(currentNode.rightChild==null){
                    currentNode.rightChild = new Node(val);
                    break;
                }else
                    currentNode = currentNode.rightChild;
            }
        }
    }

    // 搜索;             searchDeep：使用引用的方式返回本次搜索经历的搜索深度
    public Node<T> search(T val, AtomicInteger searchDeep){
        Node<T> currentRoot = treeRoot;
        while (currentRoot!=null){
            searchDeep.incrementAndGet();
            if(currentRoot.val.compareTo(val)==0)
                return currentRoot;
            else if(currentRoot.val.compareTo(val)<0)
                currentRoot = currentRoot.rightChild;
            else
                currentRoot = currentRoot.leftChild;
        }
        return null;
    }

    public Node<T> remove(T val){
        Node<T> currentNode = treeRoot;
        Node<T> parent = null;
        for(;;){
            // 找到目标值
            if(currentNode.val.compareTo(val)==0){
                if(parent==null){
                    // 删除根节点
                    treeRoot = null;
                }else{
                    // 删除叶子节点
                    if(currentNode.leftChild==null && currentNode.rightChild==null){
                        if(currentNode.val.compareTo(parent.val)<=0)
                            parent.leftChild=null;
                        else
                            parent.rightChild=null;
                    }
                    // 左子树不为空
                    else if(currentNode.leftChild!=null){
                        // 左右子树都存在
                        if(currentNode.rightChild!=null){
                           Node<T> leftChildRightest = currentNode.leftChild;
                           for(;;){
                               if( leftChildRightest.rightChild!=null )
                                   leftChildRightest = leftChildRightest.rightChild;
                               else
                                   break;
                           }
                           leftChildRightest.rightChild = currentNode.rightChild;
                        }
                        // 将currentNode的左子树放到父节点中
                        if (currentNode.val.compareTo(parent.val) <= 0)
                            parent.leftChild = currentNode.leftChild;
                        else
                            parent.rightChild = currentNode.leftChild;
                    }
                    // 右子树不为空（左子树一定为空）
                    else{
                        if(currentNode.val.compareTo(parent.val)<=0)
                            parent.leftChild=currentNode.rightChild;
                        else
                            parent.rightChild=currentNode.rightChild;
                    }
                }
                return currentNode;
            }
            // 在右边
            else if (currentNode.val.compareTo(val)<0){
                parent = currentNode;
                currentNode = currentNode.rightChild;
            }
            // 在左边
            else{
                parent = currentNode;
                currentNode = currentNode.leftChild;
            }
        }
    }

    // 按行打印二叉树
    public List<List<Node<T>>> orderLevel(){
        ArrayList<List<Node<T>>> result = new ArrayList<>();
        Deque<Node<T>> queue = new ArrayDeque<>();
        Node<T> currentRoot = treeRoot;
        queue.addLast(currentRoot);
        while (!queue.isEmpty()){
            int levelSize = queue.size();
            ArrayList<Node<T>> levelNodes = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                Node<T> topNode = queue.removeFirst();
                // visit
                levelNodes.add(topNode);
                if (topNode.leftChild!=null)
                    queue.addLast(topNode.leftChild);
                if(topNode.rightChild!=null)
                    queue.addLast(topNode.rightChild);
            }
            result.add(levelNodes);
        }
        return result;
    }

}
